// https://leetcode.cn/problems/sqrtx/description/

// 算法思路总结：
// 1. 二分查找求解整数平方根
// 2. 查找最后一个平方小于等于x的整数
// 3. 使用左闭右开区间维护查找边界
// 4. 注意使用long long防止中间结果溢出
// 5. 时间复杂度：O(log x)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int mySqrt(int x) 
    {
        if (x == 0) return 0;

        int l = 0, r = x;
        while (l + 1 != r)
        {
            long long mid = (l + r) >> 1;
            if (mid * mid <= x)
            {
                l = mid;
            }
            else
            {
                r = mid;
            }
        }

        return l == 0 ? r : l;
    }
};

int main()
{
    int x1 = 4, x2 = 8;
    Solution sol;

    cout << sol.mySqrt(x1) << endl;
    cout << sol.mySqrt(x2) << endl;

    return 0;
}